{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Form Largest Integer With Digits That Add up to Target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数位成本和为目标值的最大数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>cost</code> 和一个整数 <code>target</code> 。请你返回满足如下规则可以得到的 <strong>最大</strong> 整数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>给当前结果添加一个数位（<code>i + 1</code>）的成本为 <code>cost[i]</code> （<code>cost</code> 数组下标从 0 开始）。</li>\n",
    "\t<li>总成本必须恰好等于 <code>target</code> 。</li>\n",
    "\t<li>添加的数位中没有数字 0 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>由于答案可能会很大，请你以字符串形式返回。</p>\n",
    "\n",
    "<p>如果按照上述要求无法得到任何整数，请你返回 \"0\" 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cost = [4,3,2,5,6,7,2,5,5], target = 9\n",
    "<strong>输出：</strong>\"7772\"\n",
    "<strong>解释：</strong>添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 \"7772\" 的代价为 2*3+ 3*1 = 9 。 \"977\" 也是满足要求的数字，但 \"7772\" 是较大的数字。\n",
    "<strong> 数字     成本</strong>\n",
    "  1  ->   4\n",
    "  2  ->   3\n",
    "  3  ->   2\n",
    "  4  ->   5\n",
    "  5  ->   6\n",
    "  6  ->   7\n",
    "  7  ->   2\n",
    "  8  ->   5\n",
    "  9  ->   5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cost = [7,6,5,5,5,6,8,7,8], target = 12\n",
    "<strong>输出：</strong>\"85\"\n",
    "<strong>解释：</strong>添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。\"85\" 的成本为 7 + 5 = 12 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cost = [2,4,6,2,4,6,4,4,4], target = 5\n",
    "<strong>输出：</strong>\"0\"\n",
    "<strong>解释：</strong>总成本是 target 的条件下，无法生成任何整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cost = [6,10,15,40,40,40,40,40,40], target = 47\n",
    "<strong>输出：</strong>\"32211\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>cost.length == 9</code></li>\n",
    "\t<li><code>1 <= cost[i] <= 5000</code></li>\n",
    "\t<li><code>1 <= target <= 5000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [form-largest-integer-with-digits-that-add-up-to-target](https://leetcode.cn/problems/form-largest-integer-with-digits-that-add-up-to-target/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [form-largest-integer-with-digits-that-add-up-to-target](https://leetcode.cn/problems/form-largest-integer-with-digits-that-add-up-to-target/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,2,5,6,7,2,5,5]\\n9', '[7,6,5,5,5,6,8,7,8]\\n12', '[2,4,6,2,4,6,4,4,4]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        f = [0] + [-0x3f3f3f3f] * (target + 1)\n",
    "        for i in range(target + 1):\n",
    "            for j in range(9):\n",
    "                if cost[j] > i:\n",
    "                    continue\n",
    "                f[i] = max(f[i], f[i - cost[j]] + 1)\n",
    "        if f[target] <= 0:\n",
    "            return \"0\"\n",
    "        ans = \"\"\n",
    "        for i in range(9, 0, -1):\n",
    "            c = cost[i - 1]\n",
    "            while target >= c and f[target - c] + 1 == f[target]:\n",
    "                ans += str(i)\n",
    "                target -= c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        # 可以重复选，完全背包问题\n",
    "        # 求最大价值（最长）和具体方案\n",
    "        f = [0] + [-inf]*target\n",
    "        for x in cost:\n",
    "            for j in range(x,target + 1): # 正序\n",
    "                f[j] = max(f[j],f[j - x] + 1)\n",
    "        if f[-1] < 0:\n",
    "            return '0'\n",
    "        ans,j = '',target\n",
    "        # 构造答案\n",
    "        for i in range(len(cost) - 1,-1,-1):\n",
    "            while j >= cost[i] and f[j] == f[j - cost[i]] + 1:\n",
    "                ans += str(i + 1)\n",
    "                j -= cost[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [-float('inf')] * (target + 1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1, 10):\n",
    "            c = cost[i - 1]\n",
    "            for j in range(c, target + 1):\n",
    "                dp[j] = max(dp[j], dp[j - c] + 1)\n",
    "\n",
    "        if dp[target] < 0:\n",
    "            return \"0\"\n",
    "\n",
    "        res = ''\n",
    "        for i in range(9, 0, -1):\n",
    "            c = cost[i - 1]\n",
    "            while target >= c and dp[target] == dp[target - c] + 1:\n",
    "                res += str(i)\n",
    "                target -= cost[i - 1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        \"\"\"完全背包 + 贪心\"\"\"\n",
    "        # f(i, j): 前i个数字， 总cost恰好为 j 的最大长度\n",
    "\n",
    "        # 求最大长度\n",
    "        f = [float('-inf')] * (target + 1)\n",
    "        f[0] = 0\n",
    "        for i in range(1, 10):\n",
    "            i_cost = cost[i - 1]\n",
    "            for j in range(i_cost, target + 1):\n",
    "                f[j] = max(f[j], f[j - i_cost] + 1)\n",
    "\n",
    "        # 求答案构造\n",
    "        if f[target] < 0:\n",
    "            return '0'\n",
    "        ans = ''\n",
    "        all_cost = target\n",
    "        for i in range(9, 0, -1):\n",
    "            i_cost = cost[i - 1]\n",
    "            while all_cost >= i_cost and f[all_cost] == f[all_cost - i_cost] + 1:\n",
    "                ans += str(i)\n",
    "                all_cost -= i_cost\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [-inf] * (target + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, 10):\n",
    "            for j in range(cost[i - 1], target + 1):\n",
    "                dp[j] = max(dp[j], dp[j - cost[i - 1]] + 1)\n",
    "        if dp[-1] <= 0: return '0'\n",
    "        ans = ''\n",
    "        j = target\n",
    "        for i in range(9, 0, -1):\n",
    "            while j >= cost[i - 1] and dp[j] == dp[j - cost[i - 1]] + 1:\n",
    "                ans += str(i)\n",
    "                j -= cost[i - 1]\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [-inf] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, 10):\n",
    "            for j in range(cost[i - 1], target + 1):\n",
    "                dp[j] = max(dp[j], dp[j - cost[i - 1]] + 1)\n",
    "        if dp[target] < 0: return \"0\"\n",
    "        res = []\n",
    "        for i in range(9, 0, -1):\n",
    "            c = cost[i - 1]\n",
    "            while target >= c and dp[target] == dp[target - c] + 1:\n",
    "                res.append(str(i))\n",
    "                target -= c\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "该问题可以看作是恰好装满背包容量为 target，物品重量为 cost[i]，价值为 1 的完全背包问题。\n",
    "定义二维数组 dp，其中 dp[i+1][j] 表示使用前 i 个数位且花费总成本恰好为 j 时的最大位数，\n",
    "若花费总成本无法为 j，则规定其为 −∞。特别地，dp[0][] 为不选任何数位的状态，\n",
    "因此除了 dp[0][0] 为 0，其余 dp[0][j] 全为 −∞。\n",
    "'''\n",
    "class Solution:\n",
    "    def largestNumber2(self, cost: List[int], target: int) -> str:\n",
    "        dp = [[float(\"-inf\")] * (target + 1) for _ in range(10)]\n",
    "        where = [[0] * (target + 1) for _ in range(10)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i, c in enumerate(cost):\n",
    "            for j in range(target + 1):\n",
    "                if j < c:\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "                    where[i + 1][j] = j\n",
    "                else:\n",
    "                    if dp[i][j] > dp[i + 1][j - c] + 1:\n",
    "                        dp[i + 1][j] = dp[i][j]\n",
    "                        where[i + 1][j] = j\n",
    "                    else:\n",
    "                        dp[i + 1][j] = dp[i + 1][j - c] + 1\n",
    "                        where[i + 1][j] = j - c\n",
    "        \n",
    "        if dp[9][target] < 0:\n",
    "            return \"0\"\n",
    "        \n",
    "        ans = list()\n",
    "        i, j = 9, target\n",
    "        while i > 0:\n",
    "            if j == where[i][j]:\n",
    "                i -= 1\n",
    "            else:\n",
    "                ans.append(str(i))\n",
    "                j = where[i][j]\n",
    "        \n",
    "        return \"\".join(ans)\n",
    "        \n",
    "    \n",
    "    '''\n",
    "    由于 dp[i+1][] 每个元素值的计算只与 dp[i+1][] 和 dp[i][] 的元素值有关，\n",
    "    因此可以使用滚动数组的方式，去掉 dp 的第一个维度。\n",
    "\n",
    "    去掉 from 数组。在状态倒退时，直接根据 dp[j] 与 dp[j−cost[i]]+1 是否相等来判断，\n",
    "    若二者相等则说明是从 dp[j−cost[i]] 转移而来，即选择了第 i 个数位。\n",
    "    '''\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [float(\"-inf\")] * (target + 1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for c in cost:\n",
    "            for j in range(c, target + 1):\n",
    "                dp[j] = max(dp[j], dp[j - c] + 1)\n",
    "        \n",
    "        if dp[target] < 0:\n",
    "            return \"0\"\n",
    "        \n",
    "        ans = list()\n",
    "        j = target\n",
    "        for i in range(8, -1, -1):\n",
    "            c = cost[i]\n",
    "            while j >= c and dp[j] == dp[j - c] + 1:\n",
    "                ans.append(str(i + 1))\n",
    "                j -= c\n",
    "\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [-inf] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, 10):\n",
    "            for j in range(cost[i - 1], target + 1):\n",
    "                dp[j] = max(dp[j], dp[j - cost[i - 1]] + 1)\n",
    "        if dp[target] < 0: return \"0\"\n",
    "        res = []\n",
    "        for i in range(9, 0, -1):\n",
    "            c = cost[i - 1]\n",
    "            while target >= c and dp[target] == dp[target - c] + 1:\n",
    "                res.append(str(i))\n",
    "                target -= c\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        f = [0] + [-0x3f3f3f3f] * (target + 1)\n",
    "        for i in range(target + 1):\n",
    "            for j in range(9):\n",
    "                if cost[j] > i:\n",
    "                    continue\n",
    "                f[i] = max(f[i], f[i - cost[j]] + 1)\n",
    "        if f[target] <= 0:\n",
    "            return \"0\"\n",
    "        ans = []\n",
    "        for i in range(9, 0, -1):\n",
    "            c = cost[i - 1]\n",
    "            while target >= c and f[target - c] + 1 == f[target]:\n",
    "                ans.append(str(i))\n",
    "                target -= c\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [float(\"-inf\")] * (target + 1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for c in cost:\n",
    "            for j in range(c, target + 1):\n",
    "                dp[j] = max(dp[j], dp[j - c] + 1)\n",
    "        \n",
    "        if dp[target] < 0:\n",
    "            return \"0\"\n",
    "        \n",
    "        ans = list()\n",
    "        j = target\n",
    "        for i in range(8, -1, -1):\n",
    "            c = cost[i]\n",
    "            while j >= c and dp[j] == dp[j - c] + 1:\n",
    "                ans.append(str(i + 1))\n",
    "                j -= c\n",
    "\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        # cost = [4,3,2,5,6,7,2,5,5], target = 9\n",
    "        # 第 1 步：使用动态规划计算最大位数\n",
    "        # dp[i][j] 表示：使用数组 cost 前缀区间 [0..i] 里的元素能够刚好凑成和为 j 的时候的数字的 最大位数。\n",
    "        dp = [[-float('inf')] * (target + 1) for _ in range(10)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, 10):\n",
    "            c = cost[i - 1]\n",
    "            for j in range(target + 1):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                if j >= c and dp[i][j - c] != -float('inf'):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][j - c] + 1)\n",
    "            # print(dp)  # [0, -inf, 1, 1, 2, 2, 3, 3, 4, 4]]\n",
    "\n",
    "        if dp[9][target] < 0:\n",
    "            return '0'\n",
    "\n",
    "        # 根据第 1 步计算的结果，优先考虑数值大的放在高位，还原最大整数\n",
    "        t = target\n",
    "        res = ''\n",
    "        # cost = [4,3,2,5,6,7,2,5,5], target = 9\n",
    "        for i in range(9, 0, -1):\n",
    "            c = cost[i - 1]\n",
    "            while t >= c and dp[i][t - c] == dp[i][t] - 1:\n",
    "                t -= c\n",
    "                res += str(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [-inf] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, 10):\n",
    "            for j in range(cost[i - 1], target + 1):\n",
    "                dp[j] = max(dp[j], dp[j - cost[i - 1]] + 1)\n",
    "        if dp[target] < 0: return \"0\"\n",
    "        res = []\n",
    "        for i in range(9, 0, -1):\n",
    "            c = cost[i - 1]\n",
    "            while target >= c and dp[target] == dp[target - c] + 1:\n",
    "                res.append(str(i))\n",
    "                target -= c\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        num_digits = [float('-inf')] * (target + 1)\n",
    "        num_digits[0] = 0\n",
    "        for c in cost:\n",
    "            for k in range(c, target + 1):\n",
    "                num_digits[k] = max(num_digits[k], num_digits[k - c] + 1)\n",
    "        if num_digits[target] < 0:\n",
    "            return \"0\"\n",
    "        ans = []\n",
    "        end = target\n",
    "        for d in range(9, 0, -1):\n",
    "            c = cost[d - 1]\n",
    "            while end >= c and num_digits[end] == num_digits[end - c] + 1:\n",
    "                ans.append(d)\n",
    "                end -= c\n",
    "        \n",
    "        return \"\".join(map(str, ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str: \n",
    "        # dp[j]表示成本j的情况下能够获得最大位数是多少，位数越多。值越大。\n",
    "        dp=[-sys.maxsize]*(target+1) \n",
    "        dp[0]=0\n",
    "        for c in (cost):\n",
    "            for j in range(target+1):\n",
    "                if j-c>=0:\n",
    "                    dp[j]=max(dp[j],dp[j-c]+1)\n",
    "        # 位数确定了，那么怎么知道当前每个位数需要的值\n",
    "        if dp[target]<0:\n",
    "            return \"0\"\n",
    "        ans=[]\n",
    "        j=target\n",
    "        # 值要大，那么就是每一位的值尽可能大\n",
    "        for i in range(8,-1,-1):\n",
    "            c=cost[i]\n",
    "            while j-c>=0 and dp[j]==dp[j-c]+1:\n",
    "                ans.append(str(i+1))\n",
    "                j-=c\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "\n",
    "        dp =[float(\"-inf\")] * (target + 1)\n",
    "        fromd =[[0]*(target+1) for _ in range(10)]\n",
    "        dp[0] = 0\n",
    "\n",
    "        for c  in cost:\n",
    "            for j in range(c,target+1):\n",
    "                dp[j] = max(dp[j],dp[j-c]+1)\n",
    "\n",
    "        if dp[target]<0:\n",
    "            return \"0\"\n",
    "\n",
    "        ans = []\n",
    "        j = target\n",
    "        for i in range(8,-1,-1):\n",
    "            c = cost[i]\n",
    "            while j>=c and dp[j] == dp[j-c]+1:\n",
    "                ans.append(str(i+1))\n",
    "                j-=c\n",
    "        return \"\".join(ans)\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [[float('-inf')] * (target + 1) for _ in range(10)]\n",
    "        where = [[0] * (target + 1) for _ in range(10)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i, c in enumerate(cost):\n",
    "            for j in range(target + 1):\n",
    "                if j < c:\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "                    where[i + 1][j] = j\n",
    "                else:\n",
    "                    if dp[i][j] > dp[i + 1][j - c] + 1:\n",
    "                        dp[i + 1][j] = dp[i][j]\n",
    "                        where[i + 1][j] = j\n",
    "                    else:\n",
    "                        dp[i + 1][j] = dp[i + 1][j - c] + 1\n",
    "                        where[i + 1][j] = j - c\n",
    "        if dp[9][target] <= 0:\n",
    "            return \"0\"\n",
    "        \n",
    "        ans = []\n",
    "        i, j = 9, target\n",
    "        while i > 0:\n",
    "            if j == where[i][j]:\n",
    "                i -= 1\n",
    "            else:\n",
    "                ans.append(str(i))\n",
    "                j = where[i][j]\n",
    "        return \"\".join(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [[float(\"-inf\")] * (target + 1) for _ in range(10)]\n",
    "        where = [[0] * (target + 1) for _ in range(10)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i, c in enumerate(cost):\n",
    "            for j in range(target + 1):\n",
    "                if j < c:\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "                    where[i + 1][j] = j\n",
    "                else:\n",
    "                    if dp[i][j] > dp[i + 1][j - c] + 1:\n",
    "                        dp[i + 1][j] = dp[i][j]\n",
    "                        where[i + 1][j] = j\n",
    "                    else:\n",
    "                        dp[i + 1][j] = dp[i + 1][j - c] + 1\n",
    "                        where[i + 1][j] = j - c\n",
    "        \n",
    "        if dp[9][target] < 0:\n",
    "            return \"0\"\n",
    "        \n",
    "        ans = list()\n",
    "        i, j = 9, target\n",
    "        while i > 0:\n",
    "            if j == where[i][j]:\n",
    "                i -= 1\n",
    "            else:\n",
    "                ans.append(str(i))\n",
    "                j = where[i][j]\n",
    "        \n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "\n",
    "        dp =[[float(\"-inf\")] * (target + 1) for _ in range(10)]\n",
    "        fromd =[[0]*(target+1) for _ in range(10)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i,c  in enumerate(cost):\n",
    "            for j in range(target+1):\n",
    "                if j<c:\n",
    "                    dp[i+1][j] = dp[i][j]\n",
    "                    fromd[i+1][j] = j\n",
    "                else:\n",
    "                    if dp[i][j]>dp[i+1][j-c]+1:\n",
    "                        dp[i+1][j]=dp[i][j]\n",
    "                        fromd[i+1][j]=j\n",
    "                    else:\n",
    "                        dp[i+1][j]=dp[i+1][j-c]+1\n",
    "                        fromd[i+1][j] = j-c#选择了这个数\n",
    "\n",
    "\n",
    "\n",
    "        if dp[9][target]<0:\n",
    "            return \"0\"\n",
    "\n",
    "        ans = []\n",
    "        i,j=9,target\n",
    "        while i>0:\n",
    "            if j==fromd[i][j]:\n",
    "                i-=1\n",
    "            else:\n",
    "                ans.append(str(i))\n",
    "                j =fromd[i][j]\n",
    "\n",
    "        return \"\".join(ans)\n",
    "\n",
    "        while i>0:\n",
    "            c= cost[i]\n",
    "            if j==fromd[i][j]:\n",
    "                i-=1\n",
    "            else:\n",
    "                ans.append(str(i))\n",
    "                j =fromd[i][j]\n",
    "\n",
    "        return \"\".join(ans)\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [[float(\"-inf\")] * (target + 1) for _ in range(10)]\n",
    "        where = [[0] * (target + 1) for _ in range(10)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i, c in enumerate(cost):\n",
    "            for j in range(target + 1):\n",
    "                if j < c:\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "                    where[i + 1][j] = j\n",
    "                else:\n",
    "                    if dp[i][j] > dp[i + 1][j - c] + 1:\n",
    "                        dp[i + 1][j] = dp[i][j]\n",
    "                        where[i + 1][j] = j\n",
    "                    else:\n",
    "                        dp[i + 1][j] = dp[i + 1][j - c] + 1\n",
    "                        where[i + 1][j] = j - c\n",
    "        \n",
    "        if dp[9][target] < 0:\n",
    "            return \"0\"\n",
    "        \n",
    "        ans = list()\n",
    "        i, j = 9, target\n",
    "        while i > 0:\n",
    "            if j == where[i][j]:\n",
    "                i -= 1\n",
    "            else:\n",
    "                ans.append(str(i))\n",
    "                j = where[i][j]\n",
    "        \n",
    "        return \"\".join(ans)\n",
    "'''\n",
    "作者：力扣官方题解\n",
    "链接：https://leetcode.cn/problems/form-largest-integer-with-digits-that-add-up-to-target/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        f = [[-inf] * (target + 1) for _ in range(10)]\n",
    "        f[0][0] = 0\n",
    "        g = [[0] * (target + 1) for _ in range(10)]\n",
    "        for i, c in enumerate(cost, 1):\n",
    "            for j in range(target + 1):\n",
    "                if j < c or f[i][j - c] + 1 < f[i - 1][j]:\n",
    "                    # 不选数字i\n",
    "                    f[i][j] = f[i - 1][j]\n",
    "                    g[i][j] = j\n",
    "                else:\n",
    "                    # 选一个数字i\n",
    "                    f[i][j] = f[i][j - c] + 1\n",
    "                    g[i][j] = j - c\n",
    "        if f[9][target] < 0:\n",
    "            return '0'\n",
    "        ans = []\n",
    "        i, j = 9, target\n",
    "        while i:\n",
    "            if j == g[i][j]:\n",
    "                i -= 1\n",
    "            else:\n",
    "                ans.append(str(i))\n",
    "                j = g[i][j]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        \n",
    "        # dp[i + 1][j]: 使用前 i 个数位且花费总成本恰好为 j 时的最大位数\n",
    "        dp = [[-inf] * (target + 1) for _ in range(10)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        b = [[0] * (target + 1) for _ in range(10)]\n",
    "\n",
    "        for i in range(9):\n",
    "            c = cost[i]\n",
    "            for j in range(target + 1):\n",
    "                if j < c:\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "                    b[i + 1][j] = j\n",
    "                else:\n",
    "                    if dp[i][j] > dp[i + 1][j - c] + 1:\n",
    "                        dp[i + 1][j] = dp[i][j]\n",
    "                        b[i + 1][j] = j\n",
    "                    else:\n",
    "                        dp[i + 1][j] = dp[i + 1][j - c] + 1\n",
    "                        b[i + 1][j] = j - c\n",
    "\n",
    "        if dp[-1][target] < 0:\n",
    "            return '0'\n",
    "\n",
    "        res = []\n",
    "        i, j = 9, target\n",
    "\n",
    "        while i > 0:\n",
    "            if j == b[i][j]:\n",
    "                i -= 1\n",
    "            else:\n",
    "                res.append(f'{i}')\n",
    "                j = b[i][j]\n",
    "\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [[float(\"-inf\")] * (target + 1) for _ in range(10)]\n",
    "        where = [[0] * (target + 1) for _ in range(10)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i, c in enumerate(cost):\n",
    "            for j in range(target + 1):\n",
    "                if j < c:\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "                    where[i + 1][j] = j\n",
    "                else:\n",
    "                    if dp[i][j] > dp[i + 1][j - c] + 1:\n",
    "                        dp[i + 1][j] = dp[i][j]\n",
    "                        where[i + 1][j] = j\n",
    "                    else:\n",
    "                        dp[i + 1][j] = dp[i + 1][j - c] + 1\n",
    "                        where[i + 1][j] = j - c\n",
    "        \n",
    "        if dp[9][target] < 0:\n",
    "            return \"0\"\n",
    "        \n",
    "        ans = list()\n",
    "        i, j = 9, target\n",
    "        while i > 0:\n",
    "            if j == where[i][j]:\n",
    "                i -= 1\n",
    "            else:\n",
    "                ans.append(str(i))\n",
    "                j = where[i][j]\n",
    "        \n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [[-float(\"inf\")]*10 for _ in range(target+1)]\n",
    "        rev = [[0]*10 for _ in range(target+1)]\n",
    "        dp[0][0] = 0\n",
    "        for  i in range(1,10):\n",
    "            for j in range(target+1):\n",
    "                if j < cost[i-1]:\n",
    "                    dp[j][i] = dp[j][i-1]\n",
    "                    rev[j][i] = j\n",
    "                else:\n",
    "                    if dp[j][i-1] > dp[j-cost[i-1]][i] + 1:\n",
    "                        dp[j][i] = dp[j][i-1]\n",
    "                        rev[j][i] = j\n",
    "                    else:\n",
    "                        dp[j][i] = dp[j-cost[i-1]][i] + 1\n",
    "                        rev[j][i] = j-cost[i-1]\n",
    "        #print(dp)\n",
    "        if dp[target][9] < 0:\n",
    "            return \"0\"\n",
    "        i = 9\n",
    "        res = \"\"\n",
    "        j = target\n",
    "        while i:\n",
    "            if rev[j][i] == j:\n",
    "                i -= 1\n",
    "            else:\n",
    "                j = rev[j][i]\n",
    "                res += str(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        import sys\n",
    "        sys.set_int_max_str_digits(5000)\n",
    "        dp=[-inf]*(target+1)\n",
    "        dp[0]=0\n",
    "        for i in range(9,0,-1):\n",
    "            for j in range(cost[i-1],target+1):\n",
    "                dp[j]=max(dp[j],dp[j-cost[i-1]]*10+i)\n",
    "        return str(dp[target]) if dp[target]>0 else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        sys.set_int_max_str_digits(5000)\n",
    "        dp = [0] + [float('-inf')] * target\n",
    "\n",
    "        for i in range(9,0, -1):\n",
    "            co = cost[i-1]\n",
    "            for j in range(co, target+1):\n",
    "                dp[j]=max(dp[j], dp[j-co]*10+i)\n",
    "            # print(dp)\n",
    "        \n",
    "        return str(dp[-1]) if dp[-1]>0 else '0'\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sys.set_int_max_str_digits(6000)\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        f = [-inf] * (target + 1)\n",
    "        f[0] = 0\n",
    "        for i in range(1, target+1):\n",
    "            for j in range(1, 10):\n",
    "                if i - cost[j - 1] >= 0:\n",
    "                    f[i] = max(f[i], f[i - cost[j - 1]] * 10 + j)\n",
    "        return str(f[target] if f[target] > 0 else 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        t = []\n",
    "        had = set()\n",
    "        for i in range(8,-1,-1):\n",
    "            if cost[i] not in had:\n",
    "                t.append((cost[i], i))\n",
    "            had.add(cost[i])\n",
    "        t.sort(key=lambda x: (x[0], -x[1]))\n",
    "        cur = []\n",
    "\n",
    "        ans = \"0\"\n",
    "        # @cache\n",
    "        def dfs(i: int, j: int):\n",
    "            nonlocal ans\n",
    "            if i == 0:\n",
    "                ans = \"\".join(sorted(cur, reverse=True)) if len(cur) > len(ans) or (len(cur) == len(ans) and \"\".join(sorted(cur, reverse=True)) > ans) else ans\n",
    "            if i<0 or j >= len(t) or i < t[j][0] : return\n",
    "            if len(cur)+i//t[j][0]<len(ans):return\n",
    "            # 选择 j\n",
    "            cur.append(str(t[j][1]+1))\n",
    "            dfs(i - t[j][0], j)\n",
    "            cur.pop()\n",
    "            # 不选择j\n",
    "            dfs(i, j + 1)\n",
    "\n",
    "        dfs(target, 0)\n",
    "        # return str(\"\".join(sorted(ans, reverse=True)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        t = []\n",
    "        had = set()\n",
    "        for i in range(8,-1,-1):\n",
    "            if cost[i] not in had:\n",
    "                t.append((cost[i], i))\n",
    "            had.add(cost[i])\n",
    "        t.sort(key=lambda x: (x[0], -x[1]))\n",
    "        cur = []\n",
    "        del had\n",
    "        ans = \"0\"\n",
    "        def dfs(i: int, j: int):\n",
    "            nonlocal ans\n",
    "            if i == 0:\n",
    "                if len(cur)<len(ans):return\n",
    "                temp = \"\".join(sorted(cur, reverse=True))\n",
    "                if len(cur)>len(ans)or(len(cur) == len(ans) and temp > ans):\n",
    "                    ans = temp\n",
    "            if i<0 or j >= len(t) or i < t[j][0] : return\n",
    "            if len(cur)+i//t[j][0]<len(ans):return\n",
    "            # 选择 j\n",
    "            cur.append(str(t[j][1]+1))\n",
    "            dfs(i - t[j][0], j)\n",
    "            cur.pop()\n",
    "            # 不选择j\n",
    "            dfs(i, j + 1)\n",
    "\n",
    "        dfs(target, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        t = []\n",
    "        had = set()\n",
    "        for i in range(8,-1,-1):\n",
    "            if cost[i] not in had:\n",
    "                t.append((cost[i], i))\n",
    "            had.add(cost[i])\n",
    "        t.sort(key=lambda x: (x[0], -x[1]))\n",
    "        cur = []\n",
    "\n",
    "        ans = \"0\"\n",
    "        # @cache\n",
    "        def dfs(i: int, j: int):\n",
    "            nonlocal ans\n",
    "            if i == 0:\n",
    "                if len(cur)<len(ans):return\n",
    "                temp = \"\".join(sorted(cur, reverse=True))\n",
    "                if len(cur)>len(ans)or(len(cur) == len(ans) and temp > ans):\n",
    "                    ans = temp\n",
    "            if i<0 or j >= len(t) or i < t[j][0] : return\n",
    "            if len(cur)+i//t[j][0]<len(ans):return\n",
    "            # 选择 j\n",
    "            cur.append(str(t[j][1]+1))\n",
    "            dfs(i - t[j][0], j)\n",
    "            cur.pop()\n",
    "            # 不选择j\n",
    "            dfs(i, j + 1)\n",
    "\n",
    "        dfs(target, 0)\n",
    "        # return str(\"\".join(sorted(ans, reverse=True)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sys.set_int_max_str_digits(10000)\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        f = [0] + [float('-inf')]*target\n",
    "        for n, c in reversed(list(enumerate(cost, 1))):\n",
    "            for j in range(c, target+1):\n",
    "                f[j] = max([f[j], f[j-c]*10+n])\n",
    "        return str(f[-1]) if f[-1]>float('-inf') else \"0\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        d = {}\n",
    "        for i, c in enumerate(cost):\n",
    "            d[c] = i + 1\n",
    "        cn = list(sorted(d.items()))\n",
    "        ls = len(cn)\n",
    "        \n",
    "        ans = []\n",
    "        ans_len = 0\n",
    "        # 只能选择cn[i:], 还需要使用rest成本，已选数字choice，已选数字长度length\n",
    "        def backtrack(i, rest, choice, length):\n",
    "            nonlocal ls, ans, ans_len\n",
    "            # print(i, rest, choice, length)\n",
    "            if length + (rest // cn[i][0]) < ans_len:\n",
    "                return\n",
    "\n",
    "            if rest == 0:\n",
    "                print(length, choice)\n",
    "                if length == ans_len:\n",
    "                    ans.append(choice.copy())\n",
    "                elif length > ans_len:\n",
    "                    ans_len = length\n",
    "                    ans.clear()\n",
    "                    ans.append(choice.copy())\n",
    "                return\n",
    "\n",
    "            for j in range(i, ls):\n",
    "                c, num = cn[j]\n",
    "                if rest >= c:\n",
    "                    choice[num] += 1\n",
    "                    backtrack(j, rest - c, choice, length + 1)\n",
    "                    choice[num] -= 1\n",
    "\n",
    "        choice = {}\n",
    "        for c, num in cn:\n",
    "            choice[num] = 0\n",
    "        backtrack(0, target, choice, 0)\n",
    "        # print(ans)\n",
    "        nums = list(sorted(d.values(), reverse=True))\n",
    "\n",
    "        if ans:\n",
    "            alls = [''.join(str(num) * row[num] for num in nums) for row in ans]\n",
    "            return max(alls)\n",
    "        else:\n",
    "            return '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#数位成本和为目标值的最大数字,完全背包求具体方案，输入：cost = [4,3,2,5,6,7,2,5,5], target = 9，输出：\"7772\"，输入：cost = [7,6,5,5,5,6,8,7,8], target = 12输出：\"85\"\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp=[0]+[float('-inf')]*target#其他是最小值\n",
    "        for i in range(9,0,-1):#本题的小trick，倒序遍历cost，因为一个数字的全排列中，按数字降序排列值最大\n",
    "            for j in range(1,target+1):\n",
    "                if j>=cost[i-1]:dp[j]=max(dp[j],dp[j-cost[i-1]]*10+i)\n",
    "        cnts=collections.Counter(cost)\n",
    "        if cnts[1]==len(cost):return ''.join(['9']*target)\n",
    "        return str(dp[target])if dp[target]>0 else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp=['0']*(target+1)\n",
    "        cost_map={c:i+1 for i,c in enumerate(cost)}\n",
    "        #print('cost',cost_map)\n",
    "        def merge(s,bit):\n",
    "            if s=='0':\n",
    "                return '0'\n",
    "            for i in range(len(s)):\n",
    "                ch=s[i]\n",
    "                if int(ch)<=bit:\n",
    "                    return s[:i]+str(bit)+s[i:]\n",
    "            return s+str(bit)\n",
    "        for i in range(1,target+1):\n",
    "            for c,bit in cost_map.items():\n",
    "                tmp=''\n",
    "                if i-c==0:\n",
    "                    tmp=str(bit)\n",
    "                elif i-c>0:\n",
    "                    tmp=merge(dp[i-c],bit)\n",
    "                if len(tmp)>len(dp[i]):\n",
    "                    dp[i]=tmp\n",
    "                elif len(tmp)==len(dp[i]):\n",
    "                    buf=[tmp,dp[i]]\n",
    "                    buf.sort()\n",
    "                    dp[i]=buf[1]\n",
    "        return dp[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp=['0']*(target+1)\n",
    "        cost_map={c:i+1 for i,c in enumerate(cost)}\n",
    "        def merge(s,bit):\n",
    "            if s=='0':\n",
    "                return '0'\n",
    "            for i in range(len(s)):\n",
    "                ch=s[i]\n",
    "                if int(ch)<=bit:\n",
    "                    return s[:i]+str(bit)+s[i:]\n",
    "            return s+str(bit)\n",
    "        for i in range(1,target+1):\n",
    "            for c,bit in cost_map.items():\n",
    "                tmp=''\n",
    "                if i-c==0:\n",
    "                    tmp=str(bit)\n",
    "                elif i-c>0:\n",
    "                    tmp=merge(dp[i-c],bit)\n",
    "                if len(tmp)>len(dp[i]):\n",
    "                    dp[i]=tmp\n",
    "                elif len(tmp)==len(dp[i]):\n",
    "                    buf=[tmp,dp[i]]\n",
    "                    buf.sort()\n",
    "                    dp[i]=buf[1]\n",
    "        return dp[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [None for _ in range(target + 1)]\n",
    "        dp[0] = \"\"\n",
    "        for i in range(len(cost) - 1, -1, -1):\n",
    "            d = str(i + 1)\n",
    "            c = cost[i]\n",
    "            for j in range(c, target + 1):\n",
    "                if dp[j - c] is None:\n",
    "                    continue\n",
    "                if dp[j] is None or len(dp[j - c]) + 1 > len(dp[j]):\n",
    "                    dp[j] = dp[j - c] + d\n",
    "                elif len(dp[j - c]) == len(dp[j]) - 1 and dp[j - c] > dp[j][:-1]:\n",
    "                    dp[j] = dp[j - c] + d\n",
    "                    \n",
    "        if dp[target] is None:\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [\"0\"] * (target + 1)\n",
    "        dp[0] = \"\"\n",
    "        \n",
    "        for j in range(1, target + 1):\n",
    "            for i in range(1, 10):\n",
    "                c = cost[i-1]\n",
    "                if j < c or dp[j-c] == \"0\":\n",
    "                    continue\n",
    "                \n",
    "                # 尝试在 dp[j-c] 基础上添加一个数位 i\n",
    "                candidate = str(i) + dp[j-c]\n",
    "                \n",
    "                # 更新 dp[j]\n",
    "                if len(candidate) > len(dp[j]):\n",
    "                    dp[j] = candidate\n",
    "                elif len(candidate) == len(dp[j]) and candidate > dp[j]:\n",
    "                    dp[j] = candidate\n",
    "                    \n",
    "        return dp[-1]\n",
    "\n",
    "# 测试\n",
    "sol = Solution()\n",
    "print(sol.largestNumber([4, 3, 2, 5, 6, 7, 2, 5, 5], 9))  # 应该输出 \"7772\"\n",
    "print(sol.largestNumber([7, 6, 5, 5, 5, 6, 8, 7, 8], 12))  # 应该输出 \"85\"\n",
    "print(sol.largestNumber([2, 4, 6, 2, 4, 6, 4, 4, 4], 5))  # 应该输出 \"0\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [''] + ['0'] * target\n",
    "        for i in range(1, target + 1):\n",
    "            for j in range(9):\n",
    "                if i >= cost[j] and dp[i - cost[j]] != '0':\n",
    "                    r = str(j + 1) + dp[i - cost[j]]\n",
    "                    if len(r) > len(dp[i]) or (len(r) == len(dp[i]) and r > dp[i]):\n",
    "                        dp[i] = r\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        n = len(cost)\n",
    "        dp = [\"#\"] * (target + 1)\n",
    "        dp[0] = \"\"\n",
    "        for i in range(n):\n",
    "            for j in range(1, target + 1):\n",
    "                if j >= cost[i] and dp[j - cost[i]] != \"#\":\n",
    "                    x = str(i + 1) + dp[j - cost[i]]\n",
    "                    if len(x) > len(dp[j]) or len(x) == len(dp[j]) and x > dp[j] :\n",
    "                        dp[j] = x\n",
    "        return \"0\" if dp[target] == \"#\" else dp[target]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "sys.set_int_max_str_digits(10000)\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp=['-']*(target+1)\n",
    "        for i in range(1,target+1):\n",
    "            for j in range(9):\n",
    "                c=cost[j]\n",
    "                if i-c==0:\n",
    "                    old=dp[i]\n",
    "                    if old=='-': old='0'\n",
    "                    tmp=str(j+1)\n",
    "                    if int(tmp)>int(old):\n",
    "                        dp[i]=tmp\n",
    "                elif i-c>=0:\n",
    "                    old=dp[i]\n",
    "                    if old=='-': old='0'\n",
    "                    tmp=dp[i-c]+str(j+1)\n",
    "                    if int(tmp)>int(old):\n",
    "                        dp[i]=tmp\n",
    "        # print(dp)\n",
    "        if dp[-1]=='-':return '0'\n",
    "        return dp[-1]\n",
    "        # return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "            def str_compare(str1,str2):\n",
    "                if len(str1)>len(str2):\n",
    "                    return True\n",
    "                elif  len(str1)<len(str2):\n",
    "                    return False\n",
    "                else:\n",
    "                    return str1>str2\n",
    "            answer = [\"\" for _ in range(target + 1)]\n",
    "            min_target = min(cost)\n",
    "            max_i = 0\n",
    "            for i in range(len(cost)):\n",
    "                if cost[i] == min_target:\n",
    "                    if i > max_i:\n",
    "                        max_i = i\n",
    "            answer[min_target] = \"\" + str(max_i + 1)\n",
    "            for tar in range(min_target + 1, target + 1):\n",
    "                cur_ans = \"\"\n",
    "                for ind in range(len(cost)):\n",
    "                    if tar == cost[ind]:\n",
    "                        if str_compare(str(ind+1),cur_ans):\n",
    "                            cur_ans = str(ind + 1)\n",
    "                    if tar>=cost[ind] and answer[tar - cost[ind]]!=\"\":\n",
    "                        if str_compare(answer[tar - cost[ind]] + str(ind + 1),cur_ans):\n",
    "                            cur_ans = answer[tar - cost[ind]] + str(ind + 1)\n",
    "\n",
    "                answer[tar] = cur_ans\n",
    "            if answer[target] == \"\":\n",
    "                return \"0\"\n",
    "            else:\n",
    "                return answer[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sys.set_int_max_str_digits(6000)\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        f = ['#'] * (target + 1)\n",
    "        f[0] = ''\n",
    "        def strmax(a, b):\n",
    "            if len(a) == len(b):\n",
    "                return max(a, b)\n",
    "            if len(a) < len(b): return b\n",
    "            return a\n",
    "        for i in range(9, 0, -1):\n",
    "            for j in range(cost[i - 1], target + 1):\n",
    "                if f[j - cost[i - 1]] != '#':\n",
    "                    f[j] = strmax(f[j], f[j - cost[i - 1]] + str(i))\n",
    "        return f[target] if f[target] != '#' else '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        def compare(str1,str2):\n",
    "            if not str1:\n",
    "                return str2\n",
    "            if not str2:\n",
    "                return str1\n",
    "            if len(str1)>len(str2):\n",
    "                return str1\n",
    "            if len(str1)<len(str2):\n",
    "                return str2\n",
    "            for i in range(len(str1)):\n",
    "                if str1[i]>str2[i]:\n",
    "                    return str1\n",
    "                if str1[i]<str2[i]:\n",
    "                    return str2\n",
    "            return str1    \n",
    "        dp = [''] + [None] * target\n",
    "        for i in range(9, 0, -1):\n",
    "            for j in range(1, target+1):\n",
    "                if j >= cost[i - 1]:\n",
    "                    dp[j] = compare(dp[j], (dp[j-cost[i - 1]]) + str(i) if dp[j-cost[i - 1]] is not None else None)\n",
    "        return dp[target] if dp[target] is not None else '0'\n",
    "\n",
    "        # rs = {}\n",
    "\n",
    "        # def compare(nums):\n",
    "        #     if not nums:\n",
    "        #         return False\n",
    "        #     maxlen = 0\n",
    "        #     maxnums = []\n",
    "        #     for num in nums:\n",
    "        #         if len(num)>maxlen:\n",
    "        #             maxlen=len(num)\n",
    "        #             maxnums = [num]\n",
    "        #         elif len(num)==maxlen:\n",
    "        #             maxnums.append(num)\n",
    "        #     indicies = []\n",
    "        #     maxval = ''\n",
    "        #     for i in range(maxlen):\n",
    "        #         maxval+='0'\n",
    "        #         for j,maxnum in enumerate(maxnums):\n",
    "        #             if maxnum[i]>maxval[-1]:\n",
    "        #                 maxval = maxval[:-1]+maxnum[i]\n",
    "        #                 indicies = [j]\n",
    "        #             elif maxnum[i]==maxval[-1]:\n",
    "        #                 indicies.append(j)\n",
    "        #         if len(indicies)==1:\n",
    "        #             return maxnums[indicies[0]]\n",
    "        #     return maxnums[indicies[0]]\n",
    "\n",
    "        # def number(cost, target):\n",
    "            \n",
    "        #     if (len(cost)-1,target) in rs.keys():\n",
    "        #         return rs[(len(cost)-1,target)]\n",
    "        #     if target == 0:\n",
    "        #         rs[(len(cost)-1,target)]=''\n",
    "        #         return rs[(len(cost)-1,target)]\n",
    "        #     if target<0:\n",
    "        #         rs[(len(cost)-1,target)]=False\n",
    "        #         return rs[(len(cost)-1,target)]\n",
    "        #     if len(cost)==1:\n",
    "        #         if target%cost[0]!=0:\n",
    "        #             rs[(0,target)]=False\n",
    "        #         else:\n",
    "        #             rs[(0,target)]=''.join([str(1)]*(target//cost[0]))\n",
    "        #     else:\n",
    "        #         val1 = number(cost[:-1],target)\n",
    "        #         tmp = [val1] if val1 else []\n",
    "        #         remain_target = target-cost[-1]\n",
    "        #         count = 1\n",
    "        #         while remain_target>=0:\n",
    "        #             val2 = number(cost[:-1],remain_target)\n",
    "        #             if isinstance(val2, str):\n",
    "        #                 tmp.append(''.join([str(len(cost))]*count)+val2)\n",
    "        #                 # print(''.join([str(len(cost))]*count),len(cost),count,val2,tmp[-1])\n",
    "        #             count+=1\n",
    "        #             remain_target-=cost[-1]\n",
    "        #         rs[(len(cost)-1,target)]=compare(tmp)\n",
    "        #     # print(cost,target,rs[(len(cost)-1,target)])\n",
    "        #     return rs[(len(cost)-1,target)]\n",
    "\n",
    "        # result = number(cost, target)\n",
    "        # print(rs)\n",
    "        # if not result:\n",
    "        #     return '0'\n",
    "        # else:\n",
    "        #     return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [\"0\"] * (target + 1)\n",
    "        dp[0] = \"\"\n",
    "        \n",
    "        for j in range(1, target + 1):\n",
    "            for i in range(1, 10):\n",
    "                c = cost[i-1]\n",
    "                if j < c or dp[j-c] == \"0\":\n",
    "                    continue\n",
    "                \n",
    "                # 尝试在 dp[j-c] 基础上添加一个数位 i\n",
    "                candidate = str(i) + dp[j-c]\n",
    "                \n",
    "                # 更新 dp[j]\n",
    "                if len(candidate) > len(dp[j]):\n",
    "                    dp[j] = candidate\n",
    "                elif len(candidate) == len(dp[j]) and candidate > dp[j]:\n",
    "                    dp[j] = candidate\n",
    "                    \n",
    "        return dp[-1]\n",
    "\n",
    "# 测试\n",
    "sol = Solution()\n",
    "print(sol.largestNumber([4, 3, 2, 5, 6, 7, 2, 5, 5], 9))  # 应该输出 \"7772\"\n",
    "print(sol.largestNumber([7, 6, 5, 5, 5, 6, 8, 7, 8], 12))  # 应该输出 \"85\"\n",
    "print(sol.largestNumber([2, 4, 6, 2, 4, 6, 4, 4, 4], 5))  # 应该输出 \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\r\n",
    "        n = len(cost)\r\n",
    "        dp = [\"#\"] * (target + 1)\r\n",
    "        dp[0] = \"\"\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(cost[i], target + 1):\r\n",
    "                if dp[j - cost[i]] != \"#\":\r\n",
    "                    x = str(i + 1) + dp[j - cost[i]]\r\n",
    "                    if len(x) > len(dp[j]) or len(x) == len(dp[j]) and x > dp[j - cost[i]]:\r\n",
    "                        dp[j] = x \r\n",
    "        return \"0\" if dp[target] == \"#\" else dp[target]\r\n",
    "\r\n",
    "\r\n",
    "        # 选出长度最长\r\n",
    "        # 如果长度相同 选组合中最大值最大的\r\n",
    "        # "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        f = ['#'] * (target + 1)\n",
    "        f[0] = ''\n",
    "        def strmax(a, b):\n",
    "            if len(a) == len(b):\n",
    "                return max(a, b)\n",
    "            if len(a) < len(b): return b\n",
    "            return a\n",
    "        for i in range(9, 0, -1):\n",
    "            for j in range(cost[i - 1], target + 1):\n",
    "                if f[j - cost[i - 1]] != '#':\n",
    "                    f[j] = strmax(f[j], f[j - cost[i - 1]] + str(i))\n",
    "        return f[target] if f[target] != '#' else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sys.set_int_max_str_digits(6000)\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        f = ['#'] * (target + 1)\n",
    "        f[0] = ''\n",
    "        def strmax(a, b):\n",
    "            if len(a) > len(b):\n",
    "                return a\n",
    "            elif len(a) < len(b):\n",
    "                return b\n",
    "            for x, y in zip(a, b):\n",
    "                if x < y: return b\n",
    "                elif x > y: return a\n",
    "            return a        \n",
    "            \n",
    "        for i in range(9, 0, -1):\n",
    "            for j in range(cost[i - 1], target + 1):\n",
    "                if f[j - cost[i - 1]] != '#':\n",
    "                    f[j] = strmax(f[j], f[j - cost[i - 1]] + str(i))\n",
    "        return f[target] if f[target] != '#' else '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [0] * (target+1)\n",
    "        dpstr = [''] * (target+1)\n",
    "        for i in range(1, 10):\n",
    "            weight = cost[i-1]\n",
    "            for j in range(weight, target+1):\n",
    "                # dp[j] = max(dp[j], dp[j-weight]+1)\n",
    "                if dp[j-weight]+weight > dp[j]:\n",
    "                    dp[j] = max(dp[j], dp[j-weight]+weight)\n",
    "                    dpstr[j] = str(i)+dpstr[j-weight]\n",
    "                elif dp[j-weight]+weight == dp[j]:\n",
    "                    if len(dpstr[j-weight])+1 >= len(dpstr[j]):\n",
    "                        dpstr[j] = str(i)+dpstr[j-weight]\n",
    "        if dp[-1] < target: return '0'\n",
    "        return dpstr[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [0] * (target+1)\n",
    "        dpres = [''] * (target+1)\n",
    "        for num in range(1,10):\n",
    "            for i in range(cost[num-1], target+1):\n",
    "                # dp[i] = max(dp[i], dp[i-cost[num]])\n",
    "                if dp[i-cost[num-1]]+cost[num-1] > dp[i]:\n",
    "                    dp[i] = dp[i-cost[num-1]]+cost[num-1]\n",
    "                    dpres[i] = str(num)+dpres[i-cost[num-1]]\n",
    "                elif dp[i-cost[num-1]]+cost[num-1] == dp[i]:\n",
    "                    if len(dpres[i-cost[num-1]])+1 >= len(dpres[i]):\n",
    "                        dpres[i] = str(num)+dpres[i-cost[num-1]]\n",
    "        # print(dp)\n",
    "        # print(dpres)\n",
    "        if dp[-1] != target:\n",
    "            return '0'\n",
    "        return dpres[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [0] * (target+1)\n",
    "        dpstr = [''] * (target+1)\n",
    "        for i in range(1, 10):\n",
    "            weight = cost[i-1]\n",
    "            for j in range(weight, target+1):\n",
    "                # dp[j] = max(dp[j], dp[j-weight]+1)\n",
    "                if dp[j-weight]+weight > dp[j]:\n",
    "                    dp[j] = dp[j-weight]+weight\n",
    "                    dpstr[j] = str(i)+dpstr[j-weight]\n",
    "                elif dp[j-weight]+weight == dp[j]:\n",
    "                    if len(dpstr[j-weight])+1 >= len(dpstr[j]):\n",
    "                        dpstr[j] = str(i)+dpstr[j-weight]\n",
    "        if dp[-1] < target: return '0'\n",
    "        return dpstr[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [[0,\"\"]for i in range(target + 1)]\n",
    "        dp[target][0] = 1\n",
    "        dp[target][1] = \"0\"\n",
    "        for i in range(len(cost)):\n",
    "            if cost[i] > target:\n",
    "                continue\n",
    "            dp[cost[i]][0] = 1\n",
    "            dp[cost[i]][1] = str(i + 1)\n",
    "        for i in range(target):\n",
    "            for j in range(len(cost)):\n",
    "                if cost[j] > target:\n",
    "                    continue\n",
    "                if i >0 and dp[i][0] == 0:\n",
    "                    continue\n",
    "                if i + cost[j] > target:\n",
    "                    continue\n",
    "                add_t = i + cost[j]\n",
    "                if dp[i][0] + 1 < dp[add_t][0]:\n",
    "                    continue\n",
    "                if dp[i][0] + 1 > dp[add_t][0]:\n",
    "                    dp[add_t][0] = dp[i][0] + 1\n",
    "                    dp[add_t][1] = dp[i][1] + str(j+1)\n",
    "                    continue\n",
    "                new_str = dp[i][1] + str(j+1)\n",
    "                if new_str>dp[add_t][1]:\n",
    "                    dp[add_t][1] = dp[i][1] + str(j+1)\n",
    "        \n",
    "        return dp[target][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        t = []\n",
    "        had = set()\n",
    "        for i in range(8,-1,-1):\n",
    "            if cost[i] not in had:\n",
    "                t.append((cost[i], i))\n",
    "            had.add(cost[i])\n",
    "        t.sort(key=lambda x: (x[0], -x[1]))\n",
    "        n = len(t) \n",
    "\n",
    "        ans = \"0\"\n",
    "        # @cache\n",
    "        def dfs(i: int, j: int, cur: str):\n",
    "            nonlocal ans\n",
    "            if i == 0:\n",
    "                ans = \"\".join(sorted(cur, reverse=True)) if len(cur) > len(ans) or (len(cur) == len(ans) and \"\".join(sorted(cur, reverse=True)) > ans) else ans\n",
    "            if i<0 or j >= n or i < t[j][0] : return\n",
    "            if len(cur)+i//t[j][0]<len(ans):return\n",
    "            # 选择 j\n",
    "            dfs(i - t[j][0], j, cur + str(t[j][1]+1))\n",
    "\n",
    "            # 不选择j\n",
    "            dfs(i, j + 1, cur)\n",
    "\n",
    "        dfs(target, 0, \"\")\n",
    "        # return str(\"\".join(sorted(ans, reverse=True)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        t = []\n",
    "        had = set()\n",
    "        for i in range(8,-1,-1):\n",
    "            if cost[i] not in had:\n",
    "                t.append((cost[i], i))\n",
    "            had.add(cost[i])\n",
    "        t.sort(key=lambda x: (x[0], -x[1]))\n",
    "        n = len(t) \n",
    "        \n",
    "        ans = \"0\"\n",
    "        # @cache\n",
    "        def dfs(i: int, j: int, cur: str):\n",
    "            nonlocal ans\n",
    "            if i == 0:\n",
    "                ans = \"\".join(sorted(cur, reverse=True)) if len(cur) > len(ans) or (len(cur) == len(ans) and \"\".join(sorted(cur, reverse=True)) > ans) else ans\n",
    "            if i<0 or j >= n or i < t[j][0] : return\n",
    "            if len(cur)+i//t[j][0]<len(ans):return\n",
    "            # 选择 j\n",
    "            dfs(i - t[j][0], j, cur + str(t[j][1]+1))\n",
    "\n",
    "            # 不选择j\n",
    "            dfs(i, j + 1, cur)\n",
    "\n",
    "        dfs(target, 0, \"\")\n",
    "        # return str(\"\".join(sorted(ans, reverse=True)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(re):\n",
    "            if not re:\n",
    "                return '', 0\n",
    "            res = ''\n",
    "            c = -1\n",
    "            for i in range(8, -1, -1):\n",
    "                if re >= cost[i]:\n",
    "                    s, v = dfs(re - cost[i])\n",
    "                    if v > c:\n",
    "                        c = v\n",
    "                        res = str(i + 1) + s\n",
    "            return (res, len(res)) if res else (res, -inf)\n",
    "\n",
    "        ans, v = dfs(target)\n",
    "        dfs.cache_clear()\n",
    "        return ans if v != -inf else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def compare(s1: str, s2: str) -> bool:\n",
    "    \"\"\"数字字符串比较大小\"\"\"\n",
    "    return s1 > s2 if len(s1) == len(s2) else len(s1) > len(s2)\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dfs(remain: int) -> Tuple[bool, str]:\n",
    "            if remain <= 0:\n",
    "                return (remain == 0, '')\n",
    "\n",
    "            res = (False, '0')\n",
    "            for select in MAPPING:\n",
    "                cost = MAPPING[select]\n",
    "                isOk, nxt = dfs(remain - cost)\n",
    "                if isOk:\n",
    "                    cand = select + nxt\n",
    "                    if compare(cand, res[1]):\n",
    "                        res = (True, cand)\n",
    "\n",
    "            return res\n",
    "\n",
    "        MAPPING = {str(i + 1): num for i, num in enumerate(cost)}\n",
    "        res = dfs(target)\n",
    "        dfs.cache_clear()\n",
    "        return res[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        # 一个 cost[i] 和 str(i + 1) 对应的dict\n",
    "        # 如果存在相同cost，只保留后面的str(i + 1)\n",
    "        d = dict((v, str(i + 1)) for i, v in enumerate(cost))\n",
    "\n",
    "        # 根据cost[i] 对应 数位的大小 从小到大排列，下文用到该性质\n",
    "        cost = sorted(list(d.keys()), key=lambda i: d[i])\n",
    "\n",
    "        @cache\n",
    "        def dfs(t):\n",
    "            if not t:\n",
    "                return \"\"\n",
    "            # 默认返回\"0\"\n",
    "            s = \"0\"\n",
    "            for c in cost:\n",
    "                if (\n",
    "                    t >= c\n",
    "                    and (res := dfs(t - c)) != \"0\"\n",
    "                    # 这里要注意的是\n",
    "                    # 当res = \"\" 时， 0 + 1 >= len(\"0\")\n",
    "                    # 当存在 多个长度相同res时， 更靠后的c对应数位更大，将替换旧s\n",
    "                    and len(res) + 1 >= len(s)\n",
    "                ):\n",
    "                    s = d[c] + res\n",
    "            return s\n",
    "\n",
    "        return dfs(target)\n",
    "\n",
    "    def largestNumber1(self, cost: List[int], target: int) -> str:\n",
    "        costIdxMap = {}\n",
    "        for idx, c in enumerate(cost):\n",
    "            costIdxMap[c] = str(idx + 1)\n",
    "        cost.sort()\n",
    "        @functools.lru_cache(400)\n",
    "        def dfs(t):\n",
    "            if t == 0:\n",
    "                return ''\n",
    "            ans = '0'\n",
    "            for c in cost: # 使用贪心，每次找最小成本，这样回凑成的数字最长\n",
    "                if c <= t:\n",
    "                    tmpAns = dfs(t - c)\n",
    "                    if tmpAns != '0':\n",
    "                        if ans == '0' or len(tmpAns) + 1 > len(ans): # 如果当前字符串组成的结果长度更长，则用当前字符串拼成的结果\n",
    "                            ans = costIdxMap[c] + tmpAns\n",
    "                        elif len(tmpAns) + 1 == len(ans): # 如果当前字符串拼成的结果与当前结果长度一样，则需要比较\n",
    "                            ans = max(ans, costIdxMap[c]+tmpAns, key=int)\n",
    "            return ans\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        # 如果cost相同，一定是选择下标更大的数\n",
    "        # 根据cost去重，保留最大的下标，优先选这个\n",
    "        # 要想让数位更大，应该尽量的长，所以要尽量的做出更多的选择\n",
    "        # 在同样的数位长度的情况下，更大的下标位置排在更高位\n",
    "        # 假设选每个的贡献度为1，同时累计选择的下标\n",
    "        cnt = {}\n",
    "        for i, c in enumerate(cost, 1):\n",
    "            cnt[c] = i\n",
    "        #print(f'cnt:{cnt}')\n",
    "        def maxab(a: str, b: str) -> str:\n",
    "            if len(a) == len(b):\n",
    "                return a if a > b else b\n",
    "            else:\n",
    "                return a if len(a) > len(b) else b\n",
    "        @cache\n",
    "        def dfs(j: int) -> str:\n",
    "            if j == 0:\n",
    "                return ''\n",
    "            ans = '0'\n",
    "            #选哪个\n",
    "            for c, v in cnt.items():\n",
    "                if j >= c:\n",
    "                    f = dfs(j - c)\n",
    "                    if f != '0':\n",
    "                        if ans == '0' or len(f) + 1 > len(ans):\n",
    "                            ans = f + str(v)\n",
    "                        elif len(f) + 1 == len(ans):\n",
    "                            ans = maxab(ans, f + str(v))\n",
    "            return str(ans)\n",
    "        return dfs(target)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dfs(t):\n",
    "            if not t:\n",
    "                return ''\n",
    "            ans = '0'\n",
    "            for c in cost: # 使用贪心，每次找最小成本，这样回凑成的数字最长\n",
    "                if c <= t:\n",
    "                    tmpAns = dfs(t - c)\n",
    "                    if tmpAns != '0':\n",
    "                        # d[c]肯定大于tmpAns,所以放左边\n",
    "                        if ans == '0' or len(tmpAns) + 1 > len(ans): # 如果当前字符串组成的结果长度更长，则用当前字符串拼成的结果\n",
    "                            ans = d[c] + tmpAns\n",
    "                        elif len(tmpAns) + 1 == len(ans): # 如果当前字符串拼成的结果与当前结果长度一样，则需要比较\n",
    "                            ans = max(ans, d[c] + tmpAns, key=int)\n",
    "            return ans\n",
    "        \n",
    "        d = {}\n",
    "        for idx, c in enumerate(cost):\n",
    "            d[c] = str(idx + 1)\n",
    "        cost = sorted(d.keys())\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dfs(t):\n",
    "            if not t:\n",
    "                return ''\n",
    "            ans = '0'\n",
    "            for c in cost: # 使用贪心，每次找最小成本，这样回凑成的数字最长\n",
    "                if c <= t:\n",
    "                    tmpAns = dfs(t - c)\n",
    "                    if tmpAns != '0':\n",
    "                        # d[c]肯定大于tmpAns,所以放左边\n",
    "                        if ans == '0' or len(tmpAns) + 1 > len(ans): # 如果当前字符串组成的结果长度更长，则用当前字符串拼成的结果\n",
    "                            ans = d[c] + tmpAns\n",
    "                        elif len(tmpAns) + 1 == len(ans): # 如果当前字符串拼成的结果与当前结果长度一样，则需要比较\n",
    "                            ans = max(ans, d[c] + tmpAns, key=int)\n",
    "            return ans\n",
    "        \n",
    "        d = dict((v,str(i)) for i,v in enumerate(cost,1))\n",
    "        cost = sorted(d.keys())\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dfs(t):\n",
    "            if not t:\n",
    "                return ''\n",
    "            ans = '0'\n",
    "            for c in cost: # 使用贪心，每次找最小成本，这样回凑成的数字最长\n",
    "                if c <= t:\n",
    "                    tmpAns = dfs(t - c)\n",
    "                    if tmpAns != '0':\n",
    "                        # costIdxMap[c]肯定大于tmpAns,所以放左边\n",
    "                        if ans == '0' or len(tmpAns) + 1 > len(ans): # 如果当前字符串组成的结果长度更长，则用当前字符串拼成的结果\n",
    "                            ans = costIdxMap[c] + tmpAns\n",
    "                        elif len(tmpAns) + 1 == len(ans): # 如果当前字符串拼成的结果与当前结果长度一样，则需要比较\n",
    "                            ans = max(ans, costIdxMap[c] + tmpAns, key=int)\n",
    "            return ans\n",
    "        \n",
    "        costIdxMap = {}\n",
    "        for idx, c in enumerate(cost):\n",
    "            costIdxMap[c] = str(idx + 1)\n",
    "        cost = sorted(costIdxMap.keys()) # 使用 cost.sort()会超时报错\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dfs(curr):\n",
    "            if not curr:\n",
    "                return \"\"\n",
    "            ans = \"0\"\n",
    "            for val in cost:\n",
    "                if curr >= val:\n",
    "                    res = dfs(curr - val)\n",
    "                    if res != '0':\n",
    "                        if ans == '0' or len(res) + 1 > len(ans):\n",
    "                            ans = d[val] + res\n",
    "                        elif len(res) + 1 == len(ans):\n",
    "                            ans = max(ans, d[val] + res, key=int)\n",
    "            return str(ans)\n",
    "\n",
    "        # 重复的代价永远会取更高的那个\n",
    "        d = dict((v,str(i)) for i,v in enumerate(cost,1))\n",
    "        cost = sorted(d.keys())\n",
    "        return dfs(target)\n",
    "\n",
    "    def largestNumber2(self, cost: List[int], target: int) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dfs(t):\n",
    "            if t == 0:\n",
    "                return ''\n",
    "            ans = '0'\n",
    "            for c in cost: # 使用贪心，每次找最小成本，这样回凑成的数字最长\n",
    "                if c <= t:\n",
    "                    tmpAns = dfs(t - c)\n",
    "                    if tmpAns != '0':\n",
    "                        # costIdxMap[c]肯定大于tmpAns,所以放左边\n",
    "                        if ans == '0' or len(tmpAns) + 1 > len(ans): # 如果当前字符串组成的结果长度更长，则用当前字符串拼成的结果\n",
    "                            ans = costIdxMap[c] + tmpAns\n",
    "                        elif len(tmpAns) + 1 == len(ans): # 如果当前字符串拼成的结果与当前结果长度一样，则需要比较\n",
    "                            ans = max(ans, costIdxMap[c] + tmpAns, key=int)\n",
    "            return ans\n",
    "        \n",
    "        costIdxMap = {}\n",
    "        for idx, c in enumerate(cost):\n",
    "            costIdxMap[c] = str(idx + 1)\n",
    "        cost.sort()\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        @cache\n",
    "        def f(target):\n",
    "            if target == 0: return \"\"\n",
    "            rnt = \"0\"\n",
    "            for i in range(9):\n",
    "                if target >= cost[i]:\n",
    "                    t = f(target - cost[i])\n",
    "                    if t != \"0\": rnt = max(rnt, str(i+1) + t, key=lambda x: (len(x), x))\n",
    "            return rnt\n",
    "        return f(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        # 如果cost相同，一定是选择下标更大的数\n",
    "        # 根据cost去重，保留最大的下标，优先选这个\n",
    "        # 要想让数位更大，应该尽量的长，所以要尽量的做出更多的选择\n",
    "        # 在同样的数位长度的情况下，更大的下标位置排在更高位\n",
    "        # 假设选每个的贡献度为1，同时累计选择的下标\n",
    "        cnt = {}\n",
    "        for i, c in enumerate(cost, 1):\n",
    "            cnt[c] = i\n",
    "        #print(f'cnt:{cnt}')\n",
    "        @cache\n",
    "        def dfs(j: int) -> str:\n",
    "            if j == 0:\n",
    "                return ''\n",
    "            ans = '0'\n",
    "            #选哪个\n",
    "            for c, v in cnt.items():\n",
    "                if j >= c:\n",
    "                    f = dfs(j - c)\n",
    "                    if f != '0':\n",
    "                        if ans == '0' or len(f) + 1 > len(ans):\n",
    "                            ans = str(v) + f\n",
    "                        elif len(f) + 1 == len(ans):\n",
    "                            ans = max(ans, str(v) + f, key=int)\n",
    "            return str(ans)\n",
    "        return dfs(target)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "       @cache\n",
    "       def dfs(i: int) -> str:\n",
    "          if i == target:\n",
    "             return \"\"\n",
    "          res = \"\"\n",
    "          for j in range(0, 9):\n",
    "             if cost[j] + i <= target:\n",
    "                s = str(j + 1) + dfs(cost[j] + i)\n",
    "                if not s.__contains__(\"0\"):\n",
    "                   if len(s) > len(res) or len(s) == len(res) and s > res:\n",
    "                      res = s\n",
    "          return \"0\" if res == \"\" else res\n",
    "       return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        # 如果cost相同，一定是选择下标更大的数\n",
    "        # 根据cost去重，保留最大的下标，优先选这个\n",
    "        # 要想让数位更大，应该尽量的长，所以要尽量的做出更多的选择\n",
    "        # 在同样的数位长度的情况下，更大的下标位置排在更高位\n",
    "        # 假设选每个的贡献度为1，同时累计选择的下标\n",
    "        cnt = {}\n",
    "        for i, c in enumerate(cost):\n",
    "            cnt[c] = i + 1\n",
    "        #print(f'cnt:{cnt}')\n",
    "        @cache\n",
    "        def dfs(j: int) -> (bool,str):\n",
    "            if j <= 0:\n",
    "                return (j == 0, '')\n",
    "            find = False\n",
    "            res = ''\n",
    "            #选哪个\n",
    "            for c, v in cnt.items():\n",
    "                f, r = dfs(j - c)\n",
    "                #print(f'f:{f},r:{r}')\n",
    "                if f:\n",
    "                    find = True\n",
    "                    r = list(r)\n",
    "                    r.append(str(v))\n",
    "                    r = ''.join(sorted(r, reverse=True))\n",
    "                    if len(r) > len(res):\n",
    "                        res = r\n",
    "                    elif len(r) == len(res) and r > res:\n",
    "                        res = r\n",
    "            return (find, res)\n",
    "        f, v = dfs(target)\n",
    "        return v if f else '0'\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        # 如果cost相同，一定是选择下标更大的数\n",
    "        # 根据cost去重，保留最大的下标，优先选这个\n",
    "        # 要想让数位更大，应该尽量的长，所以要尽量的做出更多的选择\n",
    "        # 在同样的数位长度的情况下，更大的下标位置排在更高位\n",
    "        # 假设选每个的贡献度为1，同时累计选择的下标\n",
    "        cnt = {}\n",
    "        for i, c in enumerate(cost, 1):\n",
    "            cnt[c] = i\n",
    "        #print(f'cnt:{cnt}')\n",
    "        @cache\n",
    "        def dfs(j: int) -> str:\n",
    "            if j == 0:\n",
    "                return ''\n",
    "            ans = '0'\n",
    "            #选哪个\n",
    "            for c, v in cnt.items():\n",
    "                if j >= c:\n",
    "                    f = dfs(j - c)\n",
    "                    if f != '0':\n",
    "                        if ans == '0' or len(f) + 1 > len(ans):\n",
    "                            ans = f + str(v)\n",
    "                        elif len(f) + 1 == len(ans):\n",
    "                            ans = max(ans, f + str(v), key=int)\n",
    "            return str(ans)\n",
    "        return dfs(target)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, cost: List[int], target: int) -> str:\n",
    "        dp = [0] * (target+1)\n",
    "        dpres = [''] * (target+1)\n",
    "        for num in range(1,10):\n",
    "            for i in range(cost[num-1], target+1):\n",
    "                # dp[i] = max(dp[i], dp[i-cost[num]])\n",
    "                if dp[i-cost[num-1]]+cost[num-1] > dp[i]:\n",
    "                    dp[i] = dp[i-cost[num-1]]+cost[num-1]\n",
    "                    dpres[i] = str(num)+dpres[i-cost[num-1]]\n",
    "                elif dp[i-cost[num-1]]+cost[num-1] == dp[i]:\n",
    "                    if len(dpres[i-cost[num-1]])+1 >= len(dpres[i]):\n",
    "                        dpres[i] = str(num)+dpres[i-cost[num-1]]\n",
    "        print(dp)\n",
    "        print(dpres)\n",
    "        if dp[-1] != target:\n",
    "            return '0'\n",
    "        return dpres[-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
